Distributed computing systems can be difficult to maintain due to the complexity of properly synchronizing the individual devices that comprise the system. Because time-keeping across individual processes can be difficult at best, a replicated state machine approach is often used to coordinate activity among the individual devices.
A state machine can be described by a set of states, a set of commands, a set of responses, and client commands that link each response/state pair to each command/state pair. A state machine can execute a command by changing its state and producing a response. Thus, a state machine can be completely described by its current state and the action it is about to perform, removing the need to use precise time-keeping.
The current state of a state machine is, therefore, dependent upon its previous state, the commands performed since then, and the order in which those commands were performed. To maintain synchronization between two or more state machines, a common initial state can be established, and each state machine can, beginning with the initial state, execute the identical commands in the identical order.
Therefore, to synchronize one state machine to another, a determination of the commands performed by the other state machine needs to be made. The determination of commands is separate from their execution by the state machine. In particular, decision making can be performed simultaneously for multiple commands, whereas commands are executed sequentially by state machines. The problem of synchronization thus becomes a problem of determining the order of the commands performed, or, more specifically, determining the particular command performed for a given step.
Determining the commands is the heart of known solutions like the Paxos protocols. A set of servers is used to form decisions in a fault tolerant manner, as well as to maintain a record of the past decisions despite failures. Designated subsets of this server-set, called quorums, can form decisions and store them. In a reconfigurable system, the quorum-set is modifiable. A self-reconfigurable state machine controls the quorum set as part of the state it maintains. Configuration-changing commands are part of the state-machine commands.